/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-07
 * Time: 11:31
 */
public class Solution {
    // 循环取余
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n-1;
        }
        long ans = 1L;
        int p = 1000000007;
        // 循环出来 n == 4, 3, 2, 1
        // 这里面只要是 <= 4, 都不用再进行分割, 此时他们自身就是最大值了
        while (n > 4) {
            // 因为 % p 之后再 * 3 仍有可能超出 int 的范围, 所以 ans 用 long
            ans = ans * 3 % p;
            // 由数学知识可知道, 分出来的 3 越多, 那么连乘的结果就越大
            n -= 3;
        }
        return (int)(ans*n % p);
    }
}
